﻿using System;
using System.Collections.Generic;
using Algoritmia.DataStructures.Digraphs;
using Algoritmia.Problems.Traversals;
using Algoritmia.Utils;

namespace Algoritmia.Problems.SpanningTrees.GraphTraversal
{
    public class GraphTraversalSpanningForestFinder<T> : ISpanningForestFinder<T>
    {
        private readonly Func<IDigraph<T>, IGraphBreadthFirstTraverser<T, Tuple<T, T>>> _createTraverser;
        private readonly EqualityComparison<T> _equalityComparison;
        public GraphTraversalSpanningForestFinder(EqualityComparison<T> equalityComparison = null,
            Func<IDigraph<T>,IGraphBreadthFirstTraverser<T,Tuple<T,T>>> createTraverser = null)
        {
            _createTraverser = createTraverser ?? (g => new BreadthFirstTraverser<T, Tuple<T, T>>());
            _equalityComparison = AlgoritmiaFactory.GetDefaultEqualityComparison(equalityComparison);
        }
        public IEnumerable<IEnumerable<Tuple<T, T>>> SpanningForest(IDigraph<T> g)
        {
            var traverser = _createTraverser(g);
            var tree = new List<Tuple<T,T>>();
            foreach(var tuple in traverser.FullTraverse(g,(u,v) => new Tuple<T, T>(u,v)))
            {
                if ( _equalityComparison(tuple.Item1,tuple.Item2))
                {
                    if (tree.Count > 0)
                    {
                        yield return tree;
                    }
                    tree = new List<Tuple<T,T>>();
                }
                else
                {
                    tree.Add(tuple);
                }
            }
            if (tree.Count > 0)
            {
                yield return tree;
            }
        }
    }
}
